package com.example.design.leetcode.list;

//剑指 Offer 25. 合并两个排序的链表 - 解决方案
//    题目描述
//    输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
//
//    示例 1：
//    输入：1->2->4, 1->3->4
//    输出：1->1->2->3->4->4
//
//    限制：
//    0 <= 链表长度 <= 1000
//
//    标签：链表、递归
//
//    解题方案
//    思路
//    这道题可以使用递归实现，新链表也不需要构造新节点
//    终止条件：两条链表分别名为 l1 和 l2，当 l1 为空或 l2 为空时结束
//    返回值：每一层调用都返回排序好的链表头
//    本级递归内容：如果 l1 的 val 值更小，则将 l1.next 与排序好的链表头相接，l2 同理O(m+n)，m 为 l1 的长度，n 为 l2 的长度
public class Practice30 {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }

        if (l2 == null) {
            return l1;
        }

        if (l1.val < l2.val) {
            // l1比较小，让l1的下一个节点等于，l2与l1的next的排序结果
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            // l2比较小，让l2的下一个节点等于，l1与l2的next的排序结果
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }


    public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        if (l1.val < l2.val) {
            // l1小于l2, 让l1的next元素与l2进行排序
            l1.next = mergeTwoLists2(l1.next,l2);
            return l1;
        } else {
            l2.next = mergeTwoLists2(l1, l2.next);
            return l2;
        }
    }


    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l11 = new ListNode(2);
        ListNode l111 = new ListNode(4);
        l1.next = l11;
        l11.next = l111;

        ListNode l2 = new ListNode(1);
        ListNode l22 = new ListNode(3);
        ListNode l222 = new ListNode(4);
        l2.next = l22;
        l22.next = l222;

        ListNode listNode = mergeTwoLists2(l1, l2);
        System.out.println();
    }
}
